package class35;

import java.util.HashMap;
import java.util.Stack;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class LargestComponentSizebyCommonFactor {

    public static class UnionFindSet {
        public HashMap<Integer, Integer> fatherMap;//key的父亲 value
        //key是代表点的时候才有记录，value是所在集合一共有多少点
        public HashMap<Integer, Integer> sizeMap;

        public UnionFindSet(int size) {
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for (int i = 0; i < size; i++) {
                fatherMap.put(i, i);
                sizeMap.put(i, 1);
            }
        }

        public int size() {
            return sizeMap.size();
        }

        public int maxSize() {
            int ans = 0;
            for (int size : sizeMap.values()) {
                ans = Math.max(ans, size);
            }
            return ans;
        }

        private int findHead(int element) {
            Stack<Integer> path = new Stack<>();
            while (element != fatherMap.get(element)) {
                path.push(element);
                element = fatherMap.get(element);
            }
            while (!path.isEmpty()) {
                fatherMap.put(path.pop(), element);
            }
            return element;
        }

        public void union(int a, int b) {
            int aF = findHead(a);
            int bF = findHead(b);
            if (aF != bF) {
                int big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
                int small = big == aF ? bF : aF;
                fatherMap.put(small, big);
                sizeMap.put(big, sizeMap.get(aF) + sizeMap.get(bF));
                sizeMap.remove(small);
            }
        }

    }

    //求两数的公共质数
    public static int gcd(int m, int n) {
        return n == 0 ? m : gcd(n, m % n);
    }

    //arr中没有小于1的数
    public static int largestComponentSize1(int[] arr) {
        UnionFindSet set = new UnionFindSet(arr.length);
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (gcd(arr[i], arr[j]) != 1) {
                    set.union(i, j);
                }
            }
        }
        return set.maxSize();
    }

    public static int largestComponentSize2(int[] arr) {
        UnionFindSet unionFind = new UnionFindSet(arr.length);
        //key 是某个因子
        //value 是包含key因子的其中一个数的位置
        HashMap<Integer, Integer> fatorsMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            int limit = (int) Math.sqrt(num);//1~根号num
            for (int j = 1; j <= limit; j++) {//j是现在试的因子
                if (num % j == 0) {//num含有j的因子
                    if (j != 1) {//这个因子不是1
                        if (!fatorsMap.containsKey(j)) {//当前数是含有j因子的第一个数
                            fatorsMap.put(j, i);
                        } else {
                            unionFind.union(fatorsMap.get(j), i);
                        }
                    }
                    int other = num / j;//other * j == num
                    if (other != 1) {//num含有other的因子
                        if (!fatorsMap.containsKey(other)) {
                            fatorsMap.put(other, i);
                        } else {
                            unionFind.union(fatorsMap.get(other), i);
                        }
                    }
                }
            }
        }
        return unionFind.maxSize();
    }

    public static int[] generateArray(int len, int maxValue) {
        int[] res = new int[len];
        for (int i = 0; i < res.length; i++) {
            res[i] = (int) (Math.random() * maxValue) + 1;
        }
        return res;
    }

    public static int[] copyArray(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int len = 20;
        int maxValue = 30;
        int testTime = 30;
        System.out.println("test begin!");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateArray(len, maxValue);
            int[] arr2 = copyArray(arr1);
            int res1 = largestComponentSize1(arr1);
            int res2 = largestComponentSize2(arr2);
            if (res1 != res2) {
                System.out.println("Oops!");
                printArray(arr1);
                printArray(arr2);
                System.out.println(res1);
                System.out.println(res2);
                break;
            }
        }
        System.out.println("test end!");
    }
}
